| 翻訳と辞書 |
| contraction hierarchies ： ウィキペディア英語版 |
contraction hierarchies
In applied mathematics, the method of contraction hierarchies is a technique to speed up shortest-path routing by first creating precomputed "contracted" versions of the connection graph. It can be regarded as a special case of "highway-node routing".
Contraction hierarchies can be used to generate shortest-path routes much more efficiently than Dijkstra's algorithm or previous highway-node routing approaches,〔 and is used in many advanced routing techniques.〔.〕 It is publicly available in open source software to calculate routes from one place to another.
==The algorithm==
In general, scalable map routing algorithms have two distinct phases: preprocessing of the original graph (which may take more than an hour to finish) and queries (less than a second). Contraction hierarchy is an extreme case of "hierarchy" approach, which generates a multi-layered node hierarchy in the preprocessing stage. In CH every node in the graph is represented as its own level of hierarchy. This can be achieved in many ways; one simple way is simply to label each node in order of some enumeration from 1 to |N|. More sophisticated approaches might consider the type of road (highway vs minor road, etc.).〔(【引用サイトリンク】title=Efficient Route Planning, Lectures )〕〔 (CC-BY)〕
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「contraction hierarchies」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|